<?php

function insertSort($arr)
{
   $count = count($arr);
   for ($i=1;$i<$count;$i++)
   {
       //索引j和j-1的值进行比较 如果索引j的值小于前一个值，则发生交换，否则不交换
       for ($j=$i;$j>0 && $arr[$j]<$arr[$j-1];$j--)
       {
           list($arr[$j],$arr[$j-1]) = [$arr[$j-1],$arr[$j]];
       }
   }
   
   return $arr;
}

/**
 * 插入排序改进版
 */
function insertSortOptimize($arr)
{
    $count = count($arr);
    for ($i=1;$i<$count;$i++)
    {
        //保存索引为i的值，如果索引i-1的值大于i的值，不在使用交换操作
        $e = $arr[$i];
        for($j=$i;$j>0 && $arr[$j-1]>$e;$j--)
        {
            $arr[$j] = $arr[$j-1];
        }
        
        $arr[$j] = $e;
    }
    
    return $arr;
}

$arr = [1,2,3,43,121,12,-2,1,3,0.2,121,342];
//for($i=0;$i<20000;$i++)
//{
//    $arr[] = mt_rand(-10000,100000);
//}
$before_time = microtime(true);
var_dump(insertSortOptimize($arr));
$after_time = microtime(true);
$time = round($after_time-$before_time,3);
echo '耗时'.$time.'秒';